import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Stack;

public class Path {

	static List<Node> nodeList = new ArrayList<Node>();
	static Graph graph = new Graph();
	static int goalsCounter = 0;

	/*
	 * The A star search algorithm. Returns a stack of nodes. F = G+H is used to
	 * aid the search.
	 */
	public static void setNodesList() {
		nodeList.addAll(graph.nodeList);
	}

	public static Stack<Node> AStarSearch(int strtNode, int glNode) {

		ArrayList<Node> openList = new ArrayList<Node>();
		Stack<Node> closedList = new Stack<Node>();
		if (goalsCounter == 0) {
			setNodesList();
		}
		Node startNode = nodeList.get(strtNode);
		Node goalNode = nodeList.get(glNode);
		clearNodes();
		openList.removeAll(openList);
		closedList.removeAllElements();
		openList.add(startNode);
		startNode.visited = true;
		closedList.add(startNode);
		int counter = 0;
		goalsCounter++;
		Util util = new Util();
		while (closedList.peek() != goalNode) {
			Node n = (Node) closedList.peek();
			if (counter == 0) {
				closedList.get(0).visited = false;
				closedList.remove(0);
			}

			Node child = null;
			while ((child = getChildNodes(n)) != null) {
				child.visited = true;
				// Sets 15+a random number as the weight or 'g' value for the A
				// star search.
				child.setG(15 + util.showRandomInteger(0, 1));
				int HValue = 0;
				// To find the heuristic value a method similar to the Manhattan
				// method is used, and always a positive value is returned.
				HValue = goalNode.nodeNum - child.nodeNum;
				if (HValue > 0) {
					child.setH(goalNode.nodeNum - child.nodeNum);
				} else {
					child.setH(child.nodeNum - goalNode.nodeNum);
				}
				child.setF(child.getG() + child.getH());
				openList.add(child);

			}

			Collections sortedOpenList = null;

			for (int i = 0; i < openList.size(); i++) {
				if (openList.get(i) == goalNode) {
					openList.set(0, openList.get(i));
					break;
				} else {
					sortedOpenList.sort(openList, new NodeComparator());
				}
			}

			if (!openList.isEmpty()) {
				closedList.add(openList.get(0));
				openList.remove(openList.get(0));
			}
			if (openList.isEmpty()) {
				closedList.add(closedList.lastElement());
			}

			if (openList.size() > 0) {
				while (!openList.isEmpty()) {
					openList.get(0).visited = false;
					openList.remove(openList.get(0));
				}

			}
			counter++;
		}
		return closedList;

	}

	public static Node getChildNodes(Node n) {

		int j = nodeList.indexOf(n);

		for (int i = 0; i < nodeList.size(); i++) {
			if (((n.getXCor() + 1 == nodeList.get(i).getXCor() && n.getYCor() == nodeList
					.get(i).getYCor())
					|| (n.getXCor() + 1 == nodeList.get(i).getXCor() && n
							.getYCor() + 1 == nodeList.get(i).getYCor()) || (n
					.getXCor() == nodeList.get(i).getXCor() && n.getYCor() + 1 == nodeList
					.get(i).getYCor()))
					&& nodeList.get(i).visited == false
					&& graph.arrMatrix[j][i] == 1) {
				return nodeList.get(i);
			} else if (((n.getXCor() - 1 == nodeList.get(i).getXCor() && n
					.getYCor() == nodeList.get(i).getYCor()) || (n.getXCor() - 1 == nodeList
					.get(i).getXCor() && n.getYCor() + 1 == nodeList.get(i)
					.getYCor()))
					&& nodeList.get(i).visited == false
					&& graph.arrMatrix[j][i] == 1) {
				return nodeList.get(i);
			} else if (((n.getXCor() == nodeList.get(i).getXCor() && n
					.getYCor() - 1 == nodeList.get(i).getYCor()) || (n
					.getXCor() + 1 == nodeList.get(i).getXCor() && n.getYCor() - 1 == nodeList
					.get(i).getYCor()))
					&& nodeList.get(i).visited == false
					&& graph.arrMatrix[j][i] == 1) {
				return nodeList.get(i);
			} else if (((n.getXCor() - 1 == nodeList.get(i).getXCor() && n
					.getYCor() - 1 == nodeList.get(i).getYCor()) || (n
					.getXCor() - 1 == nodeList.get(i).getXCor() && n.getYCor() + 1 == nodeList
					.get(i).getYCor()))
					&& nodeList.get(i).visited == false
					&& graph.arrMatrix[j][i] == 1) {
				return nodeList.get(i);
			}
		}
		return null;
	}

	private static void clearNodes() {
		for (int i = 0; i < nodeList.size(); i++) {
			Node n = (Node) nodeList.get(i);
			n.visited = false;
		}
	}
}
